import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:堆排序
 * 时间复杂度O(nlogn)
 * 空间复杂度O(1)
 * 稳定性:不稳定
 * User: 86183
 * Date: 2023-05-02
 * Time: 14:51
 */
public class sortDeom5 {
    public static void main(String[] args) {
        int[] a = {89,15,19,18,28,34,65};
//        heapSort(a);
        deapSort(a);
        System.out.println(Arrays.toString(a));
    }
//
//    private static void heapSort(int[] a) {
//        createBigHeap(a);
//        int  end = a.length - 1;
//        while (end > 0){
//            swap(a,0,end);
//            shiftDown(a,0,end);
//            end--;
//        }
//    }
///*
//* 时间复杂度O(n)
// */
//    private static void createBigHeap(int[] a) {
//        for (int parent = (a.length-1-1)/2; parent >= 0; parent--) {
//            shiftDown(a,parent,a.length);
//
//        }
//    }
///*
//*向上调整
//* 时间复杂度O(nlogn)
//*
// */
//    private static void shiftDown(int[] a, int parent, int length) {
//        int child = 2*parent + 1;
//        while (child < length){
//            if(child+1<length && a[child] < a[child+1]){
//                child++;
//            }
//            if(a[child] > a[parent]){
//                swap(a,child,parent);
//                parent = child;
//                child = 2 * child + 1;
//            }else {
//                break;
//            }
//        }
//    }
//
//    private static void swap(int[] a, int child, int parent) {
//        int tmp = a[parent];
//        a[parent] = a[child];
//        a[child] = tmp;
//    }
    public static  void deapSort(int[] a){
        createBigDeap(a);
        int end = a.length - 1;
        while(end > 0){
            swap(a,0,end);
            shiftDown(a,0,end);
            end--;
        }
    }
    public static void createBigDeap(int[] a){
        for(int parent = (a.length-1-1)/2;parent >= 0;parent--){
            shiftDown(a,parent,a.length);
        }

    }
    public static  void shiftDown(int[] a,int parent,int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child+1 < len && a[child] < a[child+1]){
                child++;
            }
            if(a[child] > a[parent]){
                swap(a,child,parent);
            }else {
                break;
            }
        }
    }
    public static void swap(int[] a, int child ,int parent){
        int tmp = a[child];
        a[child] = a[parent];
        a[parent] = tmp;
    }
}
